package 回溯法.BFS;

import 抽象数据类型.TreeNode;

import java.util.ArrayDeque;
import java.util.Queue;

import static 树.前序遍历和中序遍历的结果还原一棵二叉树.buildTree;

/**
 * @description:
 * @author: ywk
 * @date: 2020-12-19
 */
public class 二叉树的最小深度 {
    public static void main(String[] args) {
        int[] xianxu = {1, 2, 4, 5, 6, 3};
        int[] zhongxu = {5, 4, 6, 2, 1, 3};
        int[] houxu = {5, 6, 4, 2, 3, 1};
        TreeNode treeNode = buildTree(xianxu, 0, xianxu.length - 1, zhongxu, 0, zhongxu.length - 1);
        System.out.println(minDepth(treeNode));
        System.out.println(maxDepth(treeNode));

    }

    static int minDepth(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            depth++;
            while (size-- > 0) {
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) {
                    return depth;
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return depth;
    }
    static int maxDepth(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            depth++;
            while (size-- > 0) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return depth;
    }
}
